305. Number of Islands II
Hard

You are given an empty 2D binary grid grid of size m x n. The grid represents a map where 0's represent water and 1's represent land. Initially, all the cells of grid are water cells (i.e., all the cells are 0's).

We may perform an add land operation which turns the water at position into a land. You are given an array positions where positions[i] = [ri, ci] is the position (ri, ci) at which we should operate the ith operation.

Return an array of integers answer where answer[i] is the number of islands after turning the cell (ri, ci) into a land.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

Example 1:

Input: m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
Output: [1,1,2,3]
Explanation:
Initially, the 2d grid is filled with water.
- Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land. We have 1 island.
- Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land. We still have 1 island.
- Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land. We have 2 islands.
- Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land. We have 3 islands.

Example 2:

Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]

 

Constraints:

  • 1 <= m, n, positions.length <= 104
  • 1 <= m * n <= 104
  • positions[i].length == 2
  • 0 <= ri < m
  • 0 <= ci < n

 

Follow up: Could you solve it in time complexity O(k log(mn)), where k == positions.length?

Accepted
91,949
Submissions
233,119
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions

Average Rating: 4.19 (21 votes)

Premium

Approach #1 (Brute force) [Time Limit Exceeded]

Algorithm

Reuse the code for Problem 200: Number of Islands, for each addLand operation, just call the numIslands function of Problem 200 to get the number of islands after performing that operation.

Complexity Analysis

  • Time complexity : O(L×m×n)O(L \times m \times n) where LL is the number of operations, mm is the number of rows and nn is the number of columns.

  • Space complexity : O(m×n)O(m \times n) for the grid and visited 2D arrays.


Approach #2: (Ad hoc) [Accepted]

Algorithm

Use a HashMap to map index of a land to its island_ID (starting from 0). For each addLand operation at position (row, col), check if its adjacent neighbors are in the HashMap or not and put the island_ID of identified neighbors into a set (where each element is unique):

  • if the set is empty, then the new land at position (row, col) forms a new island (monotonically increasing island_ID by 1);

  • if the set contains only one island_ID, then the new land belongs to an existing island and island_ID remains unchanged;

  • if the set contains more than one island_ID, then the new land bridges these separate islands into one island, we need to iterate through the HashMap to update this information (time consuming!) and decrease the number of island appropriately.

Complexity Analysis

  • Time complexity : O(L2)O(L^2), for each operation, we have to traverse the entire HashMap to update island id and the number of operations is LL.

  • Space complexity : O(L)O(L) for the HashMap.

P.S. C++ solution was accepted with 1409 ms runtime, but Java solution got an TLE (Time Limit Exceeded).


Approach #3: Union Find (aka Disjoint Set) [Accepted]

Intuition

Treat the 2d grid map as an undirected graph (formatted as adjacency matrix) and there is an edge between two horizontally or vertically adjacent nodes of value 1, then the problem reduces to finding the number of connected components in the graph after each addLand operation.

Algorithm

Make use of a Union Find data structure of size m*n to store all the nodes in the graph and initially each node's parent value is set to -1 to represent an empty graph. Our goal is to update Union Find with lands added by addLand operation and union lands belong to the same island.

For each addLand operation at position (row, col), union it with its adjacent neighbors if they belongs to some islands, if none of its neighbors belong to any islands, then initialize the new position as a new island (set parent value to itself) within Union Find.

For detailed description of Union Find (implemented with path compression and union by rank), you can refer to this article.

Current
1 / 15

Complexity Analysis

  • Time complexity : O(m×n+L)O(m \times n + L) where LL is the number of operations, mm is the number of rows and nn is the number of columns. it takes O(m×n)O(m \times n) to initialize UnionFind, and O(L)O(L) to process positions. Note that Union operation takes essentially constant time[1] when UnionFind is implemented with both path compression and union by rank.

  • Space complexity : O(m×n)O(m \times n) as required by UnionFind data structure.


Footnotes


  1. https://en.wikipedia.org/wiki/Disjoint-set_data_structure ↩︎

Report Article Issue

Comments: 36
vincentT's avatar
Read More

There is a bug for the third approach when we add the same position to the matrix.
I suggest we can check the duplicate in the setParent function
Like below:

void setParent(int i) {
    if (parent[i] == -1)
    {
        parent[i] = i;
        ++count;
    }
}

39
Show 1 reply
Reply
Share
Report
cja's avatar
Read More

The Union-Find solution can be just O(L) if you don't initialize the data structure upfront and do it only on demand--in my implementation when I move to a new position in the list I initialize it (with parent and rank) in the data structure, and if a node does not exist in the parent dict it is assumed to be a zero/water.

20
Show 1 reply
Reply
Share
Report
xuwd11's avatar
Read More

We can use a hashset to record all lands in approach 3 to avoid O(mn) initialization of disjoint set.

12
Show 4 replies
Reply
Share
Report
starfoe's avatar
Read More

Hmmm.... any solution hitting O(klog(mn))?

9
Show 1 reply
Reply
Share
Report
_king_'s avatar
Read More

boolean[][] visited = new boolean[nr][nc];
    for (boolean[] row : visited) {
      Arrays.fill(row, false);
    }

this is not needed, since a boolean array by default has false in it

7
Reply
Share
Report
KaitouKiddo's avatar
Read More

Solution 2 is incorrect for duplicate position test case.

3
3
[[0,0],[0,1],[1,2],[1,2]]

add this block to line 12

if (land2id.containsKey(r * n + c)) {
    result.add(num_islands);
    continue;
}

5
Reply
Share
Report
dave19's avatar
Read More

for approach #3 needs to add if (!uf.isValid(index)) uf.setParent(index);

5
Reply
Share
Report
kimjianzsu's avatar
Read More

Create parent[mn+1] and reserve parent[0] to indicate whether a cell is water.
Since the init value of new int[m * n + 1] is 0, you can avoid the array initialization of complexity O(mn).
you can achieve O(klog(mn)).

4
Show 1 reply
Reply
Share
Report
undefitied's avatar
Read More

Recently added test case with duplication position breaks all the solutions.

3
3
[[0,0],[0,1],[1,2],[1,2]]

It is easy to fix for this case (no neighbors), however, if we consider duplication cases with neighbors, and with a different number of them, all the approaches, I believe, should change.

So it the last test case valid with the problem statement?

2
Reply
Share
Report
jlfreund's avatar
Read More

For Solution #2, I think the complexity should be lower than what was described:

"...if the set contains more than one island_ID, then the new land bridges these separate islands into one island, we need to iterate through the HashMap to update this information (time consuming!) and decrease the number of island appropriately."

If the new position is a land bridge, you do not need to iterate through the entire hash map, but instead just examine at most 4 neighboring positions to update their islandID's to that of a chosen neighbor. That's 4 X O(1) operations, not an O(L) iteration of all keys in the hashtable.

2
Show 2 replies
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/12/2021 19:34Accepted108 ms38.1 MBcpp
06/06/2021 20:07Accepted156 ms38.1 MBcpp
06/06/2021 20:07Accepted80 ms37.9 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.